from collections import deque

def solution(n: int, k: int, data: list) -> int:
    # 如果 k >= n，小R可以在第一天购买所有需要的食物
    if k >= n:
        return min(data) * n

    # 使用双端队列来维护当前窗口内的最小价格
    mins = deque()
    result = 0

    for j in range(n):
        # 维护单调队列，确保队列中的元素是递增的
        while len(mins) > 0 and mins[-1][1] > data[j]:
            mins.pop()
        # 将当前元素加入队列
        mins.append([j, data[j]])
        # 移除窗口外的元素
        while mins[0][0] <= j - k:
            mins.popleft()
        # 累加当前窗口的最小价格
        result += mins[0][1]

    return result

if __name__ == '__main__':
    # 测试样例
    print(solution(n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]) == 9)
    print(solution(n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]) == 9)
    print(solution(n = 4 ,k = 1 ,data = [3, 2, 4, 1]) == 10)
    # 测试 k >= n 的情况
    print(solution(n = 4 ,k = 4 ,data = [3, 2, 4, 1]) == 4)  # 最小价格为 1，总花费为 1 * 4 = 4
    print(solution(n = 4 ,k = 5 ,data = [3, 2, 4, 1]) == 4)  # 最小价格为 1，总花费为 1 * 4 = 4
